/*
 * PageRank.h
 *
 *  Created on: Jun 14, 2011
 *      Author: lucmir
 */

#ifndef PAGERANK_H_
#define PAGERANK_H_

#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iterator>
#include <ext/hash_map>
#include <cmath>
#include <stack>
#include <string>
#include <time.h>
#include <vector>

const int DEFAULT_MAX_ITERATIONS = 500;
const double DEFAULT_EPSILON = 0.001;
const double DEFAULT_E_NORM = 0.05;
const int DEFAULT_LINKS = 100000000;

using namespace __gnu_cxx;
using namespace std;


/**
 * Types definitions
 */
typedef vector<pair<int,int> > EdgeListType;

typedef hash_multimap<int, int> AdjMapType;


class PageRank {

	/*
	 * Struct for comparing vector permutations.
	 */
	template<typename T> struct PermComparator {

		const std::vector<T>& vec;

		PermComparator(const std::vector<T>& vec) :
			vec(vec) {
		}

		bool operator()(int p0, int p1) const {
			return vec[p0] < vec[p1];
		}

	};

	/*
	 * Struct for updating out degrees.
	 */
	struct DegreeUpdater {

		vector<int>& outDeg;

		DegreeUpdater(vector<int>& outDeg) :
			outDeg(outDeg) {
		}

		void operator()(const pair<int, int>& edge) {
			++(outDeg[edge.first]);
		}

	};

	/*
	 * Struct for removing dangling links.
	 */
	struct Undangler {

		vector<int>& outDeg;

		Undangler(vector<int>& outDeg) :
			outDeg(outDeg) {
		}

		bool operator()(const pair<int, int>& edge) {
			if (outDeg[edge.second] == 0) {
				--(outDeg[edge.first]);
				return false;
			}
			return true;
		}

	};


	public:

		PageRank();
		virtual ~PageRank();

		static void calculatePageRank(std::ifstream &inFile, std::ofstream &outFile);

	private:

		static double calculateL1Norm(const vector<double>& v);
		static void readEdgeList(istream& input, EdgeListType &edges, unsigned int &maxPageNumber);


};


#endif /* PAGERANK_H_ */
